/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM23 二叉树的前序遍历
 * <a href="https://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635?tpId=295&tqId=2291302&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj&showVideoPopup=">...</a>
 * User: DELL
 * Data: 2022-11-18
 * Time: 14:04
 */

import java.util.*;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
}
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public void preorder(List<Integer> list,TreeNode root) {
        //遇到空节点返回
        if (root == null) {
            return;
        }
        //遍历根节点
        list.add(root.val);
        //遍历左子树
        preorder(list,root.left);
        //遍历右子树
        preorder(list, root.right);
        return;
    }

    public int[] preorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList<>();
        //递归前序遍历
        preorder(list,root);
        //返回结果
        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}